package com.foxzzz.temporary;

import java.util.*;

public class Solution316 {
    public String removeDuplicateLetters(String s) {
        //记录次数
        int[] count = new int[26];
        //
        int[] writed = new int[26];
        for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;
        char[] res = new char[27];

        int index = 0;
        res[index] = 0;
        int temp;

        for (int i = 0; i < s.length(); i++) {
            temp = s.charAt(i) - 'a';
            count[temp]--;
            if (writed[temp] != 0) continue;
            //count>0后面还存在
            while (index > 0 && s.charAt(i) < res[index - 1] && count[res[index - 1] - 'a'] > 0)
                writed[res[--index] - 'a'] = 0;

            res[index++] = s.charAt(i);
            writed[temp] = 1;
        }
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < index; i++) {
            str.append(res[i]);
        }
        return str.toString();
    }
    public String removeDuplicateLetters1(String s){
        Stack<Character> stack=new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            Character c=s.charAt(i);
            //保证只取第一个
            if(stack.contains(c))
                continue;
            //如果后面还有更好的选择 在这里撤销
            while(!stack.isEmpty()&&stack.peek()>c&&s.indexOf(stack.peek(),i)!=-1)
                stack.pop();
            stack.push(c);
        }
        char chars[]=new char[stack.size()];
        for (int i = 0; i < stack.size(); i++) {
            chars[i]=stack.get(i);
        }
        return new String(chars);
    }
    public static void main(String[] args) {
        System.out.println(new Solution316().removeDuplicateLetters1("abacb"));
    }
}
